import heapq
import math


class PriorityQueue:
    def __init__(self):
        self.items = []

    def enqueue(self, item, priority):
        heapq.heappush(self.items, (priority, item))

    def dequeue(self):
        if not self.is_empty():
            return heapq.heappop(self.items)[1]
        raise IndexError("无法从空优先队列出队")

    def is_empty(self):
        return len(self.items) == 0


def euclidean_distance(p1_coords, p2_coords):
    """计算两点之间的欧氏距离。p1_coords 和 p2_coords 是 (x,y) 元组。"""
    if p1_coords is None or p2_coords is None:
        return float('inf')
    return math.sqrt((p1_coords[0] - p2_coords[0]) ** 2 + (p1_coords[1] - p2_coords[1]) ** 2)


class Vehicle:
    def __init__(self, id, location, capacity, initial_max_individual_time, time=0, distance_traveled=0):
        self.id = id
        self.location = location
        self.capacity = capacity
        self.time = time
        self.max_individual_time_limit = initial_max_individual_time
        self.total_distance_traveled = distance_traveled

    def __repr__(self):
        return (f"Vehicle(id={self.id}, loc={self.location}, cap={self.capacity}, "
                f"time={self.time:.2f}, dist_travel={self.total_distance_traveled:.2f}, "
                f"time_limit={self.max_individual_time_limit:.2f})")


class State:
    def __init__(self, vehicles_list, delivered_dict, current_max_time):
        self.vehicles = sorted(vehicles_list, key=lambda v: v.id)
        self.delivered = delivered_dict
        self.max_time = current_max_time
        self.total_system_distance = sum(v.total_distance_traveled for v in self.vehicles)

    def __hash__(self):
        vehicle_details = tuple(
            (v.location, v.capacity, round(v.time, 5), round(v.total_distance_traveled, 5)) for v in self.vehicles)
        delivered_details = tuple(sorted(self.delivered.items()))
        return hash((vehicle_details, delivered_details, round(self.max_time, 5)))

    def __eq__(self, other):
        if not isinstance(other, State):
            return False
        if len(self.vehicles) != len(other.vehicles):
            return False

        vehicles_equal = all(
            s_v.id == o_v.id and
            s_v.location == o_v.location and
            s_v.capacity == o_v.capacity and
            round(s_v.time, 5) == round(o_v.time, 5) and
            round(s_v.total_distance_traveled, 5) == round(o_v.total_distance_traveled, 5)  # 确保比较距离
            for s_v, o_v in zip(self.vehicles, other.vehicles)
        )
        return (
                vehicles_equal and
                self.delivered == other.delivered and
                round(self.max_time, 5) == round(other.max_time, 5)
        )

    def __lt__(self, other):
        if not isinstance(other, State):
            return NotImplemented

        # 主要比较标准: max_time (越小越好)
        if round(self.max_time, 5) != round(other.max_time, 5):
            return round(self.max_time, 5) < round(other.max_time, 5)

        ### START STUDENT CODE HERE ###
        # 任务3: 实现次要比较标准 - 总行驶距离
        # 如果 self.max_time 与 other.max_time 近似相等，
        # 则比较 self.total_system_distance 和 other.total_system_distance。
        # 总行驶距离小的状态应该“更小”（优先级更高）。
        # (你需要确保 self.total_system_distance 和 other.total_system_distance 是可用的)
        if round(self.total_system_distance, 5) != round(other.total_system_distance, 5):
            return round(self.total_system_distance, 5) < round(other.total_system_distance, 5)  # 示例
        ### END STUDENT CODE HERE ###

        # 可选的第三比较标准: 总配送量 (越大越好)
        self_total_delivered = sum(self.delivered.values())
        other_total_delivered = sum(other.delivered.values())
        if self_total_delivered != other_total_delivered:
            return self_total_delivered > other_total_delivered

        return False  # 如果所有标准都相同

    def __repr__(self):
        return (f"State(max_time={self.max_time:.2f}, total_dist={self.total_system_distance:.2f}, "
                f"delivered={self.delivered}, vehicles={self.vehicles})")


class MultiVehiclePlanner:
    def __init__(self, nodes, graph, demands, vehicle_props):
        """
        vehicle_props: 列表，每个元素是一个元组 (capacity, max_individual_time_limit)
                       对应每辆车的容量和个体最大行驶时间。
        """
        self.nodes = nodes
        self.graph = graph
        self.demands = demands
        self.vehicle_properties = vehicle_props  # 例如 [(cap1, time_limit1), (cap2, time_limit2)]

        if self.graph:
            all_speeds = [speed for edges in self.graph.values() for _, _, speed in edges if speed > 0]
            self.min_speed = min(all_speeds) if all_speeds else 1
            self.avg_speed = sum(all_speeds) / len(all_speeds) if all_speeds else 1
        else:
            self.min_speed = 1
            self.avg_speed = 1

    def initial_state(self):
        initial_vehicles = []
        for i, (capacity, max_time_limit) in enumerate(self.vehicle_properties, start=1):
            # 在创建Vehicle实例时传递 max_individual_time_limit
            vehicle = Vehicle(id=i, location=1, capacity=capacity, initial_max_individual_time=max_time_limit, time=0,
                              distance_traveled=0)
            initial_vehicles.append(vehicle)

        initial_delivered = {village_id: 0 for village_id in self.demands}
        return State(initial_vehicles, initial_delivered, 0)

    def is_goal(self, current_state):
        for village_id, required_demand in self.demands.items():
            if current_state.delivered.get(village_id, 0) < required_demand:
                return False
        return True

    def successors(self, current_state):
        possible_next_states = []
        for vehicle_idx_in_state_list, current_vehicle_from_state in enumerate(current_state.vehicles):
            if current_vehicle_from_state.location not in self.graph:
                continue
            if current_vehicle_from_state.capacity == 0 and current_vehicle_from_state.location != 1:
                continue

            for neighbor_id, distance, speed in self.graph[current_vehicle_from_state.location]:
                if speed <= 0: continue

                new_vehicles_list = []
                for v_orig in current_state.vehicles:
                    new_vehicles_list.append(
                        Vehicle(id=v_orig.id,
                                location=v_orig.location,
                                capacity=v_orig.capacity,
                                initial_max_individual_time=v_orig.max_individual_time_limit,
                                time=v_orig.time,
                                distance_traveled=v_orig.total_distance_traveled)
                    )

                vehicle_to_move = new_vehicles_list[vehicle_idx_in_state_list]
                travel_time = distance / speed

                if vehicle_to_move.time + travel_time > vehicle_to_move.max_individual_time_limit:
                    continue

                vehicle_to_move.location = neighbor_id
                vehicle_to_move.time += travel_time
                vehicle_to_move.total_distance_traveled += distance

                new_delivered_dict = current_state.delivered.copy()

                if neighbor_id == 1:
                    original_cap, _ = self.vehicle_properties[vehicle_to_move.id - 1]
                    vehicle_to_move.capacity = original_cap
                elif neighbor_id in self.demands and vehicle_to_move.capacity > 0:
                    demand_at_target = self.demands[neighbor_id]
                    delivered_so_far = new_delivered_dict.get(neighbor_id, 0)
                    remaining_demand = demand_at_target - delivered_so_far
                    if remaining_demand > 0:
                        can_deliver = min(vehicle_to_move.capacity, remaining_demand)
                        vehicle_to_move.capacity -= can_deliver
                        new_delivered_dict[neighbor_id] += can_deliver

                new_max_overall_time = max(v.time for v in new_vehicles_list)

                if new_max_overall_time > self.deadline:
                    priority_satisfied = True
                    for p_vid in priority_village_ids_large:
                        if new_delivered_dict.get(p_vid, 0) < self.demands[p_vid]:
                            priority_satisfied = False
                            break
                    if not priority_satisfied:
                        continue  # 跳过不满足优先村庄约束的状态

                possible_next_states.append(State(new_vehicles_list, new_delivered_dict, new_max_overall_time))

        return possible_next_states

    def heuristic(self, current_state):
        # 这个启发式函数学生不需要修改，但可以分析
        total_remaining_demand = 0
        needy_village_ids = []
        for village_id, required_demand in self.demands.items():
            remaining = required_demand - current_state.delivered.get(village_id, 0)
            if remaining > 0:
                total_remaining_demand += remaining
                needy_village_ids.append(village_id)
        if total_remaining_demand == 0: return 0

        max_one_vehicle_capacity = 1
        if self.vehicle_properties:
            max_one_vehicle_capacity = max(p[0] for p in self.vehicle_properties) if self.vehicle_properties else 1
        if max_one_vehicle_capacity <= 0: max_one_vehicle_capacity = 1

        num_full_loads_needed = math.ceil(total_remaining_demand / max_one_vehicle_capacity)

        max_dist_to_needy_village = 0
        depot_coords = self.nodes.get(1)
        if depot_coords and needy_village_ids:
            current_max_dist = 0
            for v_id in needy_village_ids:
                village_coords = self.nodes.get(v_id)
                dist = euclidean_distance(depot_coords, village_coords)
                if dist != float('inf') and dist > current_max_dist:
                    current_max_dist = dist
            max_dist_to_needy_village = current_max_dist
        elif not needy_village_ids:
            return 0
        else:  # Fallback if coordinates are missing
            all_distances_in_graph = [d for edges_list in self.graph.values() for _, d, _ in edges_list if d > 0]
            max_dist_to_needy_village = max(all_distances_in_graph) if all_distances_in_graph else 10

        if max_dist_to_needy_village == 0 and total_remaining_demand > 0:
            return total_remaining_demand / (max_one_vehicle_capacity * self.min_speed + 1e-6)

        time_for_one_furthest_trip = max_dist_to_needy_village / self.min_speed
        h_value = (num_full_loads_needed * time_for_one_furthest_trip)
        if self.vehicle_properties:
            h_value /= len(self.vehicle_properties)
        return h_value

    def a_star(self):
        pq = PriorityQueue()
        start_node_state = self.initial_state()

        g_start = start_node_state.max_time
        h_start = self.heuristic(start_node_state)
        f_start = g_start + h_start

        pq.enqueue(start_node_state, f_start)
        came_from = {start_node_state: None}
        g_score = {start_node_state: g_start}

        explored_count = 0
        # 增加探索上限以应对可能更复杂的状态空间或次优启发式
        # 对于自动化测试，这个值可能需要根据测试算例的复杂度调整
        max_explored_limit = 20000

        while not pq.is_empty():
            current_s = pq.dequeue()
            explored_count += 1

            if current_s.max_time > g_score.get(current_s, float('inf')):
                continue  # Found a better path already

            if explored_count > max_explored_limit:
                print(f"探索达到上限 {max_explored_limit}，提前终止。")
                return None, float('inf'), explored_count

            if self.is_goal(current_s):
                total_path = []
                temp_current = current_s
                while temp_current is not None:
                    total_path.append(temp_current)
                    temp_current = came_from[temp_current]
                return total_path[::-1], current_s.max_time, explored_count

            for next_s in self.successors(current_s):
                tentative_g_next = next_s.max_time

                if tentative_g_next < g_score.get(next_s, float('inf')):
                    g_score[next_s] = tentative_g_next
                    came_from[next_s] = current_s
                    h_next = self.heuristic(next_s)
                    f_value_next = tentative_g_next + h_next
                    pq.enqueue(next_s, f_value_next)

        return None, float('inf'), explored_count


class NewMultiVehiclePlanner2(MultiVehiclePlanner):
    def __init__(self, nodes, graph, demands, vehicle_props):
        super().__init__(nodes, graph, demands, vehicle_props)
        self.shortest_dist = self.Dijkstra_shortest()
        self.deadline = self.culculate_priority_deadline(priority_village_ids_large)

    def culculate_priority_deadline(self, priority_village_ids):
        if not priority_village_ids:
            return float('inf')
        # 1. 总需求
        total_demand = sum(self.demands[vid] for vid in priority_village_ids if vid in self.demands)
        # 2. 最小容量
        min_capacity = min([cap for cap, _ in self.vehicle_properties]) if self.vehicle_properties else 1
        # 3. 需要的最少往返次数
        trips = math.ceil(total_demand / min_capacity)
        # 4. 最远距离
        depot_coords = self.nodes.get(1)
        max_dist = 0
        for vid in priority_village_ids:
            coords = self.nodes.get(vid)
            if coords:
                dist = euclidean_distance(depot_coords, coords)
                if dist > max_dist:
                    max_dist = dist
        # 5. 最小速度
        min_speed = self.min_speed
        # 6. 单程时间
        one_trip_time = max_dist / min_speed if min_speed > 0 else float('inf')
        # 7. deadline = 往返次数 * 单程时间 * 2（往返）
        deadline = trips * one_trip_time * 2
        return deadline

    def Dijkstra_shortest(self):
        dist_path = {node: float('inf') for node in self.nodes}
        dist_path[1] = 0
        pq = PriorityQueue()
        pq.enqueue(1, 0)
        visited = set()
        while not pq.is_empty():
            current = pq.dequeue()
            if current in visited:
                continue
            if current not in self.graph:
                continue
            visited.add(current)
            current_d = dist_path[current]
            for next_c, distance, speed in self.graph[current]:
                if speed <= 0:
                    continue
                next_dist = current_d + distance
                if next_dist < dist_path[next_c]:
                    dist_path[next_c] = next_dist
                    pq.enqueue(next_c, next_dist)

        return dist_path

    def heuristic(self, current_state):

        # 计算剩余需求
        total_remaining = 0
        priority_remaining = 0
        for vid, require in self.demands.items():
            remaining = require - current_state.delivered.get(vid, 0)
            if remaining > 0:
                total_remaining += remaining
                if vid in priority_village_ids_large:
                    priority_remaining += remaining

        if total_remaining == 0:
            return 0

        # 图中最长的一条边
        max_edge = max(d for edge in self.graph for _, d, _ in self.graph[edge])

        # 计算车辆的可用容量
        available_capacity = sum(v.capacity for v in current_state.vehicles)
        if available_capacity == 0 and total_remaining > 0:
            return float('inf')

        # 计算最远优先村庄的距离
        priority_village_dist = 0
        for vid_p in priority_village_ids_large:
            if current_state.delivered.get(vid_p, 0) < self.demands[vid_p]:
                min_priority_village_dist = self.shortest_dist.get(vid_p, max_edge)
                if min_priority_village_dist > priority_village_dist:
                    priority_village_dist = min_priority_village_dist

        # 后计算最远村庄的的距离
        max_dist = priority_village_dist
        if priority_village_dist == 0:
            max_dist = 0
        for vid in self.demands:
            if current_state.delivered.get(vid, 0) < self.demands[vid]:
                dist = self.shortest_dist.get(vid, max_edge)
                if dist > max_dist:
                    max_dist = dist

        # 5. 基础启发值（到最远村庄的时间）
        base_h = (2 * max_dist) / self.min_speed if max_dist > 0 else 0

        # 6. 需求因子（考虑优先级和车辆容量）
        demand_factor = priority_remaining * 1.3 + total_remaining
        demand_factor /= max(1, available_capacity)

        # 负载因子(平衡负载)
        capacity = [v.capacity for v in current_state.vehicles]
        if capacity:
            load_factor = max(capacity) - min(capacity)
        else:
            load_factor = 0

        return base_h + demand_factor * (max_dist / self.min_speed) + load_factor * 0.1

# -----------------------------------------------------------------------------
# 测试算例和主程序 (学生不应修改这部分，用于自动化测试)
# -----------------------------------------------------------------------------
def run_test_case(name, nodes, graph, demands, vehicle_props):
    print(f"\n--- 测试案例: {name} ---")
    planner = NewMultiVehiclePlanner2(nodes, graph, demands, vehicle_props)

    start_time = time.time()
    final_path, total_time, num_explored = planner.a_star()
    end_time = time.time()
    execution_time = end_time - start_time

    if final_path:
        final_state = final_path[-1]
        total_dist_all_vehicles = sum(v.total_distance_traveled for v in final_state.vehicles)
        print(f"  🎉 解决方案找到!")
        print(f"    最慢车辆用时: {total_time:.2f}")
        print(f"    所有车辆总行驶距离: {total_dist_all_vehicles:.2f}")
        print(f"    共探索了 {num_explored} 个状态。")
        print(f"    路径长度 (状态数): {len(final_path)}")
        print(f"    运行时间: {execution_time:.4f} 秒")
        print("    最终状态车辆详情:")
        for v in final_state.vehicles:
            print(f"      {v}")
    else:
        print(f"  😥 未能找到解决方案。共探索了 {num_explored} 个状态。")
        print(f"    运行时间: {execution_time:.4f} 秒")


if __name__ == '__main__':
    import time

    # 大规模算例数据
    nodes_data_large = {
        1: (0, 0), 2: (5, 149), 3: (118, 103), 4: (140, 132), 5: (102, 108),
        6: (90, 63), 7: (110, 140), 8: (18, 137), 9: (109, 130), 10: (100, 137),
        11: (142, 145), 12: (61, 12), 13: (40, 118), 14: (111, 10), 15: (147, 36),
        16: (123, 129), 17: (128, 81), 18: (13, 132), 19: (10, 80), 20: (70, 140),
        21: (28, 50), 22: (11, 138), 23: (111, 113), 24: (148, 108), 25: (93, 14),
        26: (149, 78), 27: (1, 104), 28: (102, 3), 29: (12, 13), 30: (81, 118),
        31: (110, 11), 32: (122, 117), 33: (136, 101), 34: (13, 101), 35: (141, 14)
    }
    graph_data_large = {
        1: [(2, 149.1, 6), (35, 141.0, 3), (29, 17.7, 7), (25, 94.0, 3), (21, 57.3, 7), (12, 62.2, 6)],
        2: [(1, 149.1, 6), (3, 120.0, 7), (8, 13.9, 7), (20, 65.2, 7), (22, 6.1, 6), (27, 45.1, 3)],
        3: [(2, 120.0, 7), (4, 30.4, 3), (5, 17.0, 5), (10, 37.6, 7), (16, 10.0, 6), (23, 7.1, 4)],
        4: [(3, 30.4, 3), (5, 41.8, 8), (7, 31.6, 5), (11, 13.3, 7), (16, 17.7, 5), (24, 24.7, 6)],
        5: [(3, 17.0, 5), (4, 41.8, 8), (6, 47.4, 8), (9, 23.0, 6), (17, 30.0, 7), (23, 10.2, 7)],
        6: [(5, 47.4, 8), (7, 54.1, 5), (12, 59.1, 7), (17, 38.0, 3), (19, 82.0, 4), (25, 49.2, 7)],
        7: [(4, 31.6, 5), (6, 54.1, 5), (8, 92.0, 5), (11, 32.0, 5), (16, 18.4, 6), (20, 40.0, 7)],
        8: [(2, 13.9, 7), (7, 92.0, 5), (9, 91.0, 5), (13, 28.6, 6), (18, 5.8, 5), (22, 7.1, 6)],
        9: [(5, 23.0, 6), (8, 91.0, 5), (10, 11.4, 6), (16, 13.0, 7), (23, 19.2, 5), (30, 30.5, 6)],
        10: [(3, 37.6, 7), (9, 11.4, 6), (11, 42.8, 7), (16, 26.4, 4), (20, 30.2, 3), (30, 24.2, 7)],
        11: [(4, 13.3, 7), (7, 32.0, 5), (10, 42.8, 7), (16, 19.9, 5), (20, 32.8, 7), (32, 33.9, 6)],
        12: [(1, 62.2, 6), (6, 59.1, 7), (14, 50.0, 6), (19, 53.1, 7), (21, 53.1, 6), (29, 49.0, 8)],
        13: [(8, 28.6, 6), (18, 27.0, 8), (19, 46.1, 5), (27, 40.8, 6), (30, 7.1, 6), (34, 27.9, 4)],
        14: [(12, 50.0, 6), (15, 43.2, 6), (17, 72.8, 5), (25, 18.4, 6), (28, 12.0, 7), (31, 0.0, 5)],
        15: [(14, 43.2, 6), (17, 50.1, 7), (26, 42.2, 4), (28, 51.1, 4), (31, 41.1, 8), (35, 23.3, 7)],
        16: [(3, 10.0, 6), (4, 17.7, 5), (7, 18.4, 6), (9, 13.0, 7), (10, 26.4, 4), (11, 19.9, 5)],
        17: [(5, 30.0, 7), (6, 38.0, 3), (14, 72.8, 5), (15, 50.1, 7), (23, 34.0, 3), (26, 21.2, 7)],
        18: [(8, 5.8, 5), (13, 27.0, 8), (19, 52.0, 7), (22, 7.8, 6), (27, 13.3, 6), (34, 31.0, 3)],
        19: [(6, 82.0, 4), (12, 53.1, 7), (13, 46.1, 5), (18, 52.0, 7), (21, 34.5, 5), (27, 26.0, 7)],
        20: [(2, 65.2, 7), (7, 40.0, 7), (10, 30.2, 3), (11, 32.8, 7), (22, 59.0, 7), (30, 30.5, 3)],
        21: [(1, 57.3, 7), (12, 53.1, 6), (19, 34.5, 5), (29, 39.8, 7), (34, 53.2, 8)],
        22: [(2, 6.1, 6), (8, 7.1, 6), (18, 7.8, 6), (20, 59.0, 7), (27, 10.0, 6)],
        23: [(3, 7.1, 4), (5, 10.2, 7), (9, 19.2, 5), (17, 34.0, 3), (30, 31.0, 8), (32, 11.0, 5)],
        24: [(4, 24.7, 6), (26, 43.2, 3), (32, 29.7, 7), (33, 14.6, 6), (35, 94.6, 5)],
        25: [(1, 94.0, 3), (6, 49.2, 7), (14, 18.4, 6), (28, 9.9, 3), (31, 18.0, 7)],
        26: [(15, 42.2, 4), (17, 21.2, 7), (24, 43.2, 3), (28, 76.2, 7), (33, 26.0, 7), (35, 20.0, 6)],
        27: [(2, 45.1, 3), (13, 40.8, 6), (18, 13.3, 6), (19, 26.0, 7), (22, 10.0, 6), (34, 12.0, 8)],
        28: [(1, 102.0, 6), (14, 12.0, 7), (15, 51.1, 4), (25, 9.9, 3), (26, 76.2, 7), (31, 7.1, 6)],
        29: [(1, 17.7, 7), (12, 49.0, 8), (21, 39.8, 7), (34, 88.1, 5)],
        30: [(9, 30.5, 6), (10, 24.2, 7), (13, 7.1, 6), (20, 30.5, 3), (23, 31.0, 8), (32, 42.0, 6)],
        31: [(14, 0.0, 5), (15, 41.1, 8), (25, 18.0, 7), (28, 7.1, 6), (35, 6.1, 6)],
        32: [(11, 33.9, 6), (23, 11.0, 5), (24, 29.7, 7), (30, 42.0, 6), (33, 18.4, 8)],
        33: [(24, 14.6, 6), (26, 26.0, 7), (32, 18.4, 8), (35, 87.4, 5)],
        34: [(13, 27.9, 4), (18, 31.0, 3), (21, 53.2, 8), (27, 12.0, 8), (29, 88.1, 5)],
        35: [(1, 141.0, 3), (15, 23.3, 7), (24, 94.6, 5), (26, 20.0, 6), (31, 6.1, 6), (33, 87.4, 5)]
    }
    demands_data_large = {
        18: 58, 20: 38, 22: 36, 34: 22, 27: 52, 8: 35, 21: 41
    }  # 8 demand points
    priority_village_ids_large = [20, 8, 18]  # 示例优先村庄
    # 估算 priority_deadline (基于上述优先村庄和节点 1)
    # nodes_concrete[1]=(0,0), nodes_concrete[20]=(70,140) -> dist 156.5
    # nodes_concrete[8]=(18,137) -> dist 138.2
    # nodes_concrete[18]=(13,132) -> dist 132.6
    # max_dist_priority = 156.5, avg_speed = 5
    # priority_deadline = (156.5 / 5) * 2.5 = 31.3 * 2.5 = 78.25
    # 在估算时间下采取更严格的限制
    priority_deadline_large = 30.0
    vehicle_props_large = [
        (78, 153.4), (86, 139.2), (52, 229.5), (70, 169.8)
    ]
    # 容量和个体最大行驶时间限制示例
    # (容量, 个体最大行驶时间

    run_test_case("大规模算例", nodes_data_large, graph_data_large, demands_data_large, vehicle_props_large)